import java.io.File;
import java.io.FileNotFoundException;
import java.text.Collator;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Kruskal_BellmanFord 
{
	final Collator collator = Collator.getInstance(Locale.GERMAN);
	//////////////////////////
	// Private Fields für Spannbaum bzw. Kruskal
	private ArrayList<Integer> weightArray = new ArrayList<Integer>();
	private HashMap<Integer, String> exitsArray = new HashMap<Integer, String>();
	private HashMap<Integer, HashMap<Integer,Integer>> adjaList = new HashMap<Integer, HashMap<Integer,Integer>>();
	private HashMap<Integer, ArrayList<Integer>> tempUnionArray = new HashMap<Integer, ArrayList<Integer>>();
	private TreeMap<Float, HashMap<Integer, ArrayList<Integer>>> tempSortedConnections = new TreeMap<Float, HashMap<Integer, ArrayList<Integer>>>();
	
	// Private Fields für Bellman-Ford
	private float[] distance;
	private int[] pred;
	private int startIndex, endIndex;
	
	private final String FILENAME = "/Users/Dennis/Documents/workspace/DSEA Übung/Blatt 11/autobahn.txt";
	
	public static void main(String argv[]) throws FileNotFoundException
	{
		Kruskal_BellmanFord obj = new Kruskal_BellmanFord();
		
		//obj.startBellmanFord("Berlin-Marzahn", "München-Süd, Kreuz");
		//System.out.println(obj.exitsArray.size());
		obj.startKruskal();
		//System.out.println(obj.isUndirectedGraph());
		System.out.println(obj.countEdges());
		obj.startBellmanFord("Berlin-Marzahn", "München-Süd, Kreuz");
		//System.out.println(obj.countEdges());
		
//		ArrayList<Integer> temp = new ArrayList<Integer>();
//		for(int i = 0; i < obj.exitsArray.size(); i++)
//		{
//			if (!temp.contains(obj.tempUnionArray.get(i).get(0).intValue()))
//				temp.add(obj.tempUnionArray.get(i).get(0).intValue());
//		}
//		System.out.println(temp);
//		System.out.println(obj.tempUnionArray);
	}
	
	private void readTxtFile() throws FileNotFoundException
	{
		Scanner s = new Scanner(new File(FILENAME));
		int countExists = s.nextInt();
		int countConnections = s.nextInt();
		
		s.nextLine();
		// Alle Abfahrten in das array "exitsArray" schreiben.
		for (int i = 0; i < countExists; i++) 
		{	
			inserNewExitNode(i, s.nextLine());
		}
		
		for (int t = 0; t < countConnections; t++)
		{
			// Die Verbindungen lesen.
			int indexFrom = s.nextInt();
			int indexTo = s.nextInt();
			String stringWeight = s.nextLine();
			int weight = Integer.parseInt(Float.toString((Float.parseFloat(stringWeight) * 10))
					.substring(0 ,Float.toString((Float.parseFloat(stringWeight) * 10)).indexOf(".")));
			
			// Die Kante prüfen ob sie gültig ist.
			if (!this.isEdgeValid(indexFrom, indexTo, weight))
				continue;
			
			// Das Feld tempSortetConnections füllen, für den Kruskal
			insertEdgeToSortedConnections(indexFrom, indexTo, weight);
			
			// Ist das Gewicht schon in dem GewichtsArray vorhanden.
			if (!this.weightArray.contains(weight))
			{
				this.weightArray.add(weight);
			}
			// Den Index des Gewichts abspeichern.
			int weightIndex = this.weightArray.indexOf(weight);
			
			// Eine neue Kante in den Graphen einfügen. Hin und Rückrichtung.
			float oldWeight = this.insertNewEdge(weightIndex, indexFrom, indexTo);
			this.insertNewEdge(weightIndex, indexTo, indexFrom);
			
			// Wenn es eine kante gibt die die gleichen Knoten verbindet mit einem geringeren Gewicht muss die alte entfernt werden.
			if (oldWeight != -1)
				this.tempSortedConnections.get(oldWeight).remove(indexTo);
		}
		s.close();
	}

	private void insertEdgeToSortedConnections(int indexFrom, int indexTo, float weight)
	{
		if (this.tempSortedConnections.containsKey(weight))
		{
			if (this.tempSortedConnections.get(weight).containsKey(indexFrom))
			{
				this.tempSortedConnections.get(weight).get(indexFrom).add(indexTo);
			}
			else
			{
			ArrayList<Integer> array = new ArrayList<Integer>();
			array.add(indexTo);
							
			this.tempSortedConnections.get(weight).put(indexFrom, array);
			}
		}
		else
		{
			HashMap<Integer, ArrayList<Integer>> temp = new HashMap<Integer, ArrayList<Integer>>();
			ArrayList<Integer> array  = new ArrayList<Integer>();
			array.add(indexTo);
			temp.put(indexFrom, array);
			
			this.tempSortedConnections.put(weight, temp);
		}
	}

	
	// Methoden für den Kurskal Algo
	
	public void startKruskal() throws FileNotFoundException
	{
		// Prüfen ob alle Felder gefüllt sind, die gebraucht werden.
		if (this.adjaList.isEmpty() || this.weightArray.isEmpty() || this.exitsArray.isEmpty())
			this.readTxtFile();
		
		// Das tempUnionFeld initialisieren
		for (int j = 0; j < this.exitsArray.size(); j++) 
		{
			ArrayList<Integer> temp = new ArrayList<Integer>();
			temp.add(j);
			this.tempUnionArray.put(j, temp);
		}
		
		// Über das Feld mit den aufsteigend sortierten Kanten nach Gewicht laufen.
		Iterator itWeight = this.tempSortedConnections.entrySet().iterator();
	    while (itWeight.hasNext()) 
	    {
	        Map.Entry pairs = (Map.Entry)itWeight.next();
	        HashMap<Integer, Integer> edges = (HashMap<Integer, Integer>) pairs.getValue();
	               
	        Iterator itEdges = edges.entrySet().iterator();
		    while (itEdges.hasNext()) 
		    {
			    Map.Entry pairsEdge = (Map.Entry)itEdges.next();
			    ArrayList<Integer> tempArray = (ArrayList<Integer>) pairsEdge.getValue();
			    
			    // Da aus einer Kante mehrere mit dem gleichen Gewicht gehen können.
			    for (int i = 0; i < tempArray.size(); i++)
			    {
			    	// Wenn size größer als eins, dann hat diese Union zwei Mitlgieder, 
			    	// ansonsten ist der eine Eintrag ein Verweis auf eine Union.
		    		if (this.tempUnionArray.get(pairsEdge.getKey()).get(0).intValue() == this.tempUnionArray.get(tempArray.get(i)).get(0).intValue())
		    		{
		    			// Dann sind beide Knoten in der gleichen Union und die Kante kann gel�scht werden.
		    			this.removeEdge((Integer)pairsEdge.getKey(), tempArray.get(i));
		    		}
		    		else
		    		{
		    			// Dann sind die beiden Knoten in unterschiedlichen Unions und müssen verschmolzen werden.
		    			this.union(this.tempUnionArray.get(pairsEdge.getKey()).get(0).intValue()
		    					, this.tempUnionArray.get(tempArray.get(i)).get(0).intValue());
		    		}
			    }
		    }		     
	    } 
	}
	
	private void inserNewExitNode(int index, String exitName)
	{
		this.exitsArray.put(index, exitName.trim());
	}
	
	private float insertNewEdge(int weightIndex, int from, int to)
	{
		if (this.adjaList.containsKey(from))
		{
			float oldweight = -1;
			if (this.adjaList.get(from).containsKey(to))
			{
				oldweight = this.weightArray.get(this.adjaList.get(from).get(to));
			}
			
			this.adjaList.get(from).put(to, weightIndex);
			return oldweight;
		}
		else 
		{
			HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
			temp.put(to, weightIndex);
			this.adjaList.put(from, temp);
		}
		
		return -1;
	}

	private void removeEdge(int from, int to)
	{
		if (!this.adjaList.containsKey(from)) 
			// Fehler, der Knoten existiert nicht in der AdjaList.
			return;
		
		if (!this.adjaList.containsKey(to)) 
			// Fehler, der Knoten existiert nicht in der AdjaList.
			return;
		
		this.adjaList.get(from).remove(to);
		this.adjaList.get(to).remove(from);
	}
	
	private void initializeTempSortExitArray()
	{	
		// Sortierte Array mit den Kanten erzeugen. 
		// Da dies ein balancedTree ist, der als Key das Gewicht übergeben bekommt muss ich mich um das sortieren nicht kümmern.
		// Sondern kann einfach alle Kanten der Reihe nach hineinschreiben. Gibt es schon das Gewicht in dem Tree wird dem Value
		// eine HashMap einfach die Kante noch hinzugefügt.
		
		
		
//		Iterator itFrom = this.adjaList.entrySet().iterator();
//	    while (itFrom.hasNext()) 
//	    {
//	        Map.Entry pairs = (Map.Entry)itFrom.next();
//	        HashMap<Integer, Integer> children = (HashMap<Integer, Integer>) pairs.getValue();
//	        
//	        Iterator itChildren = children.entrySet().iterator();
//		    while (itChildren.hasNext()) 
//		    {
//		    	Map.Entry pairsChildren = (Map.Entry)itChildren.next();
//		    	float currentWeight = this.weightArray.get(this.adjaList.get(pairs.getKey()).get(pairsChildren.getKey()));
//		    	if (this.tempSortedConnections.containsKey(currentWeight))
//				{
//					this.tempSortedConnections.get(currentWeight).put((Integer)pairs.getKey(), (Integer)pairsChildren.getKey());
//				}
//				else
//				{
//					HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
//					temp.put((Integer)pairs.getKey(), (Integer)pairsChildren.getKey());
//					this.tempSortedConnections.put(currentWeight, temp);
//				}
//		    }
//	    }
	}
	
	public boolean isUndirectedGraph()
	{
		// Alle Knoten in der AdjaListe durchlaufen.
		Iterator itFrom = this.adjaList.entrySet().iterator();
	    while (itFrom.hasNext()) 
	    {
	        Map.Entry pairs = (Map.Entry)itFrom.next();
	        HashMap<Integer, Integer> children = (HashMap<Integer, Integer>) pairs.getValue();
	        
	        // Alle Kinder eines Knotens druchlaufen.
	        Iterator itChildren = children.entrySet().iterator();
		    while (itChildren.hasNext()) 
		    {
		    	Map.Entry pairsChildren = (Map.Entry)itChildren.next();
		    	
		    	// Ist das Kind auch als Knoten in der AdjaListe vorhanden?
				if (!this.adjaList.containsKey((Integer)pairs.getKey()))
					return false;
				
				// Hat der KindKnoten auch seinen "Vater" als Kind? 
				if (!this.adjaList.get((Integer)pairs.getKey()).containsKey((Integer)pairsChildren.getKey()))
					return false;
		    }
	    }
		return true;
	}
	
	private void union(int indexExitFrom, int indexExitTo)
	{
		// Entscheiden welche Union größer als die andere ist und dann die kleiner der größeren hinzufügen.
		if (this.tempUnionArray.get(indexExitFrom).size() > this.tempUnionArray.get(indexExitTo).size())
		{
			// Alle Einträge der kleineren Union durchlaufen und der größeren hinzufügen.
			for (Integer exitIndex : this.tempUnionArray.get(indexExitTo)) 
			{
				this.tempUnionArray.get(indexExitFrom).add(exitIndex);
				
				// Wichtig, die Einträge der alten Unionmitlgieder auch auf die neue Union ändern.
				if (exitIndex != indexExitTo)
				{
					this.tempUnionArray.get(exitIndex).clear();
					this.tempUnionArray.get(exitIndex).add(indexExitFrom);
				}
			}
			
			// Die Mitlgieder der alten Union löschen und nur einen Verweis auf die neue hinterlassen.
			this.tempUnionArray.get(indexExitTo).clear();
			this.tempUnionArray.get(indexExitTo).add(indexExitFrom);
		}
		else
		{
			// Alle Einträge der kleineren Union durchlaufen und der größeren hinzufügen.
			for (Integer exitIndex : this.tempUnionArray.get(indexExitFrom)) 
			{
				this.tempUnionArray.get(indexExitTo).add(exitIndex);
				
				// Wichtig, die Einträge der alten Unionmitlgieder auch auf die neue Union ändern.
				if (exitIndex != indexExitFrom)
				{
					this.tempUnionArray.get(exitIndex).clear();
					this.tempUnionArray.get(exitIndex).add(indexExitTo);
				}
			}
						
			// Die Mitlgieder der alten Union löschen und nur einen Verweis auf die neue hinterlassen.
			this.tempUnionArray.get(indexExitFrom).clear();
			this.tempUnionArray.get(indexExitFrom).add(indexExitTo);
		}
	}

	public int countEdges()
	{
		int counter = 0;
		
		// Alle Knoten in der AdjaListe durchlaufen.
		Iterator itFrom = this.adjaList.entrySet().iterator();
	    while (itFrom.hasNext()) 
	    {
	        Map.Entry pairs = (Map.Entry)itFrom.next();
	        HashMap<Integer, Integer> children = (HashMap<Integer, Integer>) pairs.getValue();
	        
	        // Die Anzahl aller Kinder aller Knoten aufadieren.
	        counter += children.size();
	    }
	    // Die Anzahl durch zwei teilen, damit man nicht die Hin und Rückrichtung mitzählt.
		return counter / 2;
	}

	private boolean isEdgeValid(int from, int to, float weight)
	{
		// Da in dem TextFile Kanten auch ungerichtet vorkommen müssen dieses einmal üersprungen werden.
		if (!this.adjaList.containsKey(to))
			return true;
		
		if (!this.adjaList.containsKey(from))
			return true;
		
		if (this.adjaList.get(to).containsKey(from))
		{
			return this.weightArray.get(this.adjaList.get(to).get(from).intValue()) > weight;
		}
		else if (this.adjaList.get(from).containsKey(to))
		{
			return this.weightArray.get(this.adjaList.get(from).get(to).intValue()) > weight;
		}
			
    	return true;
	}	
	
	// Methoden für den Bellman - Ford Algo
	
	private void findStartAndEndExit(String from, String to)
	{
		// Den Startknoten finden
		Iterator itFrom = this.exitsArray.entrySet().iterator();
	    while (itFrom.hasNext()) 
	    {
	        Map.Entry pairs = (Map.Entry)itFrom.next();
	        collator.setStrength(Collator.SECONDARY);

	        if (collator.equals(pairs.getValue().toString(), from))
	        	this.startIndex = (Integer)pairs.getKey();
        	else if (collator.equals(pairs.getValue().toString(), to))
        		this.endIndex = (Integer)pairs.getKey();
	    } 
	}
	
	private void startBellmanFord(String from, String to) throws FileNotFoundException
	{
		// Prüfen ob alle Felder gefüllt sind, die gebraucht werden.
		if (this.adjaList.isEmpty() || this.weightArray.isEmpty() || this.exitsArray.isEmpty())
			this.readTxtFile();
		
		// Anfang und Ende finden.
		this.findStartAndEndExit(from, to);
		
		// Distance und pred Array erzeugen.
		this.distance = new float[this.exitsArray.size()];
		this.pred = new int[3000];
		
		// Alle Knoten durchlaufen. Distanz Array initialisieren
		Iterator it = this.exitsArray.entrySet().iterator();
	    while (it.hasNext()) 
	    {
	        Map.Entry pairs = (Map.Entry)it.next();
	        this.distance[(Integer)pairs.getKey()] = Float.MAX_VALUE;
	    }
	    
	    this.distance[this.startIndex] = (float) 0;
	    for (int i = 1; i < this.exitsArray.size(); i++) 
	    {
	    	// Alle Knoten in der AdjaListe durchlaufen.
			Iterator itFrom = this.adjaList.entrySet().iterator();
		    while (itFrom.hasNext()) 
		    {
		        Map.Entry pairs = (Map.Entry)itFrom.next();
		        HashMap<Integer, Integer> children = (HashMap<Integer, Integer>) pairs.getValue();
		        
		        // Alle Kinder eines Knotens druchlaufen.
		        Iterator itChildren = children.entrySet().iterator();
			    while (itChildren.hasNext()) 
			    {
			    	Map.Entry pairsChildren = (Map.Entry)itChildren.next();
			    	
			    	// Alle Kanten relaxieren
			    	this.relaxEdge((Integer)pairs.getKey(), (Integer)pairsChildren.getKey());
			    }
		    }
		}	
	    
	    // Die Entfernung ausgeben.
	    System.out.println(this.distance[this.endIndex] / 10);
	    
	    // Den Weg ausgeben.
	    //ArrayList<Integer> path = new ArrayList<Integer>();
	    //path.add(this.endIndex);
	    int currentIndex = this.endIndex;
	    int counter = 1;
	    while (currentIndex != this.startIndex)
	    {
	    	counter++;
	    	currentIndex = this.pred[currentIndex];
	    	//path.add(currentIndex);
	    }
//	    Collections.reverse(path);
//	    for (Integer index : path) 
//	    {
//	    	System.out.println(this.exitsArray.get(index));
//		}
	    System.out.println(counter);
	}
	
	private void relaxEdge(int from, int to)
	{
		if (this.distance[to] > this.distance[from] + this.weightArray.get(this.adjaList.get(from).get(to)))
		{
			this.distance[to] = this.distance[from] + this.weightArray.get(this.adjaList.get(from).get(to));
			this.pred[to] = from;
		}
	}
}
